package class13;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class Knapsack2 {
    public static int process(int[] w,int[] v,int index,
                              int alreadyW,int bag){
        if (alreadyW > bag)
            return -1;
        if (index == w.length)
            return 0;
        int p1 = process(w,v,index+1,alreadyW,bag);
        int p2next = process(w,v,index+1,alreadyW + w[index],bag);
        int p2 = -1;
        if (p2next!=-1){
            p2 = v[index] + p2next;
        }
        return Math.max(p1,p2);
    }

    public static int process1(int[] w,int[] v,int index,int rest){
        if (rest<0){
            return -1;
        }
        if (index == w.length)
            return 0;
        int p1 = process1(w,v,index+1,rest);
        int p2 = -1;
        int p2next = process1(w,v,index+1,rest - w[index]);
        if (p2next != -1){
            p2 = v[index] + p2next;
        }
        return Math.max(p1,p2);
    }
}
